
from functools import reduce


def cf2fraction(cflist: list) -> tuple():
    '''
    Limited continued fractions [d0,d1,d2,d3,d4,...,dn] = pn/qn
    return (pn,qn)

    >>> print(cf2fraction([1]))
    (1, 1)
    >>> print(cf2fraction([2]))
    (2, 1)
    >>> print(cf2fraction([1,2]))
    (3, 2)
    >>> print(cf2fraction([1,2,3]))
    (10, 7)
    '''
    lens = len(cflist)

    # reverse cflist, compute from button
    # zip(), for div() a/b --> (a, b)
    cflist = list(zip(cflist, [1]*lens))[::-1]

    # x,y -> 1/x + y
    frac = reduce(lambda x, y: (x[1]*y[1]+x[0]*y[0], x[0]*y[1]), cflist)

    # g = math.gcd(frac[0], frac[1])
    # frac = frac[0]//g, frac[1]//g

    return frac


def cf2fractionPn(cflist: list) -> int:
    '''
    cflist = [a0,a1,a2,...,an] = pn/qn
    p(n+1) = a_n+1 * pn + p_n-1  (n=0,1,2,3...)
    p_-1 = 1, p0 = a0

    return pn
    '''

    x, y = 1, cflist[0]

    lens = len(cflist)  # n+1

    for i in range(1, lens):
        x, y = y, cflist[i]*y + x

    return y


def cf2fractionQn(cflist: list) -> int:
    '''
    cflist = [a0,a1,a2,...,an] = pn/qn
    q(n+1) = a_n+1 * qn + q_n-1  (n=0,1,2,3...)
    q_-1 = 0, q0 = 1

    return qn
    '''

    x, y = 0, 1

    lens = len(cflist)  # n+1

    for i in range(1, lens):
        x, y = y, cflist[i]*y + x

    return y


if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=False)

    cflist = list(range(10))
    print(cf2fraction(cflist))
    print(cf2fractionPn(cflist))
    print(cf2fractionQn(cflist))

    from timeit import timeit
    print(timeit('cf2fraction(list(range(10)))',
                 setup='from __main__ import cf2fraction'))
    print(timeit('cf2fractionPn(list(range(10))),cf2fractionQn(list(range(10)))',
                 setup='from __main__ import cf2fractionPn,cf2fractionQn'))
    # 40.138315505999344
    # 29.163950093000494
